//============================================================================
// Name        : problem86.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <math.h>

using namespace std;
typedef struct Triangle{
	int a, b, c;
};

int partition(Triangle t) {
	if (t.b > t.a*2) return t.a/2;
	return t.a/2 + (t.a - (t.b+1)/2)+1;
}

int gcd(int a, int b){
	if (b == 0) return a;
	return gcd(b, a%b);
}

int bruteForce() {
	int count = 0;
	vector<Triangle> cubes;
	for (int a = 1; a <= 100; a++) {
		for(int b = a; b <= 100; b++) {
			for(int c = b; c <= 100; c++) {
				int l = c*c + (a+b)*(a+b);
				int tt = (int)sqrt(l);
				if (tt*tt == l) {
					count++;
					Triangle cub;
					cub.a = a;
					cub.b = b;
					cub.c = c;
					cubes.push_back(cub);
				}
			}
		}
	}
	return count;
}

vector<Triangle> generateBasicTris(int limit) {
	vector<Triangle> rightTris;
	for (int m = 1; m < limit/2; m++) {
		for (int n = m + 1; n < limit/2; n++) {
			Triangle tmp;
			tmp.a = 2*m*n;
			tmp.b = n*n - m*m;
			tmp.c = n*n + m*m;
			if (gcd(tmp.b, tmp.a) != 1 && gcd(tmp.a, tmp.c) != 1 && gcd(tmp.b, tmp.c) != 1)continue;
			if (tmp.a > tmp.b) {
				int t = tmp.a;
				tmp.a = tmp.b;
				tmp.b = t;
			}
			if (tmp.a > limit || tmp.b > limit*2) break;
			rightTris.push_back(tmp);
		}
	}
	return rightTris;
}

vector<Triangle> generateAll(Triangle basic, int limit) {
	vector<Triangle> all;
	for (int i = 1; i < limit; i++) {
		Triangle tmp;
		tmp.a = basic.a*i;
		tmp.b = basic.b*i;
		tmp.c = basic.c*i;
		if (tmp.a > limit || tmp.b > limit*2) break;
		all.push_back(tmp);
	}
	return all;
}

int findSolutions(vector<Triangle> allTris, int limit) {
	int total = 0;
	for (unsigned int i = 0; i < allTris.size(); i++) {
		if (allTris.at(i).a > limit || allTris.at(i).b > limit*2) continue;
		if ( allTris.at(i).b > limit && allTris.at(i).b < allTris.at(i).a * 2) {
			total = total + allTris.at(i).a - (allTris.at(i).b+1)/2 + 1;
		} else if (allTris.at(i).b <= limit){
			total += partition(allTris.at(i));
		}
	}
	return total;
}
int main() {
    vector<Triangle> basicTris, allTris;
    basicTris = generateBasicTris(2000);
	for (unsigned int i = 0; i < basicTris.size(); i++) {
		vector<Triangle> fromBasic = generateAll(basicTris.at(i), 2000);
		vector<Triangle>::iterator it;
		it = allTris.begin();
		allTris.insert(it, fromBasic.begin(), fromBasic.end());
	}
	for (int i = 100; i < 2000; i++) {
		if (findSolutions(allTris, i) > 1000000) {
			cout<<"Solutions: "<<i<<endl;
			break;
		}
	}
	return 0;
}
